Wherein I ignore my own advice

Problem
Code

So, we have to count the number of arrangements of a bunch of blocks. For part one, I thought I was being clever; I wrote methods that produce the next possible arrangement, and check if the current arrangement matches the input pattern.

fn valid_arrangement(pattern: &[u8], intervals: &[(usize, usize)]) -> bool {
    let mut i = 0;

    for &(lo, hi) in intervals {
        while i < lo {
            if pattern[i] == b'#' {
                return false;
            }
            i += 1;
        }

        while i <= hi {
            if pattern[i] == b'.' {
                return false;
            }
            i += 1;
        }
    }

    while i < pattern.len() {
        if pattern[i] == b'#' {
            return false;
        }
        i += 1;
    }

    true
}

fn next_arrangement(groups: &mut [(usize, usize)], length: usize) -> bool {
    for i in (0..groups.len()).rev() {
        // Check if there's space to the right.
        let end = match groups.get(i + 1) {
            Some(&(s, _)) => s - 2,
            None => length - 1,
        };

        // If so, move current group one space to the right.
        if groups[i].1 < end {
            groups[i].0 += 1;
            groups[i].1 += 1;

            // Now we have to left-align all blocks after self.
            for j in (i + 1)..groups.len() {
                let new_start = groups[j - 1].1 + 2;
                let length = groups[j].1 - groups[j].0;
                groups[j] = (new_start, new_start + length);
            }

            return true;
        }
    }

    false
}

It was relatively efficient for small inputs, but then part 2 gave me a reality check. Honestly, I should've known that actually, physically going through the arrangements was gonna be wrong. I literally said yesterday to be careful about stuff like that. And yet...

Anyway, for part two I rewrote all of it to be shorter and better. The core idea is now to consume characters one at a time, whilst remembering how many consecutive #s we've eaten. Then, we can make sensible decisions based on the characters eaten. The full core method looks like this:

type Cache = HashMap<(usize, usize, usize), usize>;

fn arrangements(s: &[u8], run: usize, groups: &[usize], cache: &mut Cache) -> usize {
    let cache_key = (s.len(), run, groups.len());

    if s.is_empty() {
        // String is empty. The current run must empty or equal to the last remaining group.
        usize::from((run == 0 && groups.is_empty()) || groups == [run])
    } else if run > *groups.first().unwrap_or(&0) {
        // Our current run is too large for the current group. The whole branch can be discarded.
        0
    } else if let Some(&cached_result) = cache.get(&cache_key) {
        cached_result
    } else {
        let (c, s) = (s[0], &s[1..]);
        let count = match (c, run) {
            (b'.', 0) => arrangements(s, 0, groups, cache),
            (b'.', n) => match n == groups[0] {
                true => arrangements(s, 0, &groups[1..], cache),
                false => 0,
            },

            (b'#', n) => arrangements(s, n + 1, groups, cache),

            // If we're not in a run, a ? could be either. Just count both options.
            (b'?', 0) => arrangements(s, 1, groups, cache) + arrangements(s, 0, groups, cache),
            // Already in a run. Whether we assume a # or . fully depends on the current group.
            (b'?', n) => match n == groups[0] {
                true => arrangements(s, 0, &groups[1..], cache),
                false => arrangements(s, n + 1, groups, cache),
            },

            _ => unreachable!(),
        };

        cache.insert(cache_key, count);
        count
    }
}

So it consists of some sanity checks, a caching mechanism, and the actual core logic:

let (c, s) = (s[0], &s[1..]);
let count = match (c, run) {
	(b'.', 0) => arrangements(s, 0, groups, cache),
	(b'.', n) => match n == groups[0] {
		true => arrangements(s, 0, &groups[1..], cache),
		false => 0,
	},

	(b'#', n) => arrangements(s, n + 1, groups, cache),

	// If we're not in a run, a ? could be either. Just count both options.
	(b'?', 0) => arrangements(s, 1, groups, cache) + arrangements(s, 0, groups, cache),
	// Already in a run. Whether we assume a # or . fully depends on the current group.
	(b'?', n) => match n == groups[0] {
		true => arrangements(s, 0, &groups[1..], cache),
		false => arrangements(s, n + 1, groups, cache),
	},

	_ => unreachable!(),
};

arrangements calls itself recursively

Here, based on the current character and the length of the current run of #s, we can easily decide what to do next:

• if we hit a ., our current run (if there is one) HAS to match the current group, in which case we can discard said group and keep going; otherwise the whole arrangement doesn't work; of course, if we don't have a run of #s, we simply skip the current character;
• if we hit a #, we simply count it and keep on reading;
• when we hit a ? it could be either a # or .. However, if we're already on a run of #s, it's actually decided—we have a group to match after all!
  For example, in ##?.. with a group of 3, we'd reach the ? with run = 2, groups = [3]. There's no point even trying out . for the ?, since the only way the whole arrangement could ever work is if it's a #.

And that's... honestly it. The caching mechanism speeds the whole thing up significantly in part 2. The smart Computer Science-y word for this is dynamic programming.